package com.lht.leetcodeDemo;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-07-03
 */
public class BinaryTreeLevelOrderTraversalII {

    @Test
    public void test(){
        TreeNode node=new TreeNode(3);
        node.left=new TreeNode(9);
        node.right=new TreeNode(20);
        node.left.left=null;
        node.left.right=null;
        node.right.left=new TreeNode(15);
        node.right.right=new TreeNode(7);

        for(List<Integer> l:levelOrderBottom(node)){
            StringBuilder sb=new StringBuilder();
            for(Integer i:l){
                sb.append(i).append(",");
            }
            System.out.println(sb.substring(0,sb.length()-1));
        }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        List<TreeNode> next=new ArrayList<>();
        next.add(root);
        while(!next.isEmpty()){
            List<TreeNode> n=new ArrayList<>();
            List<Integer> two=new ArrayList<>();
            for(TreeNode node:next){
                if(node.left!=null){
                    n.add(node.left);
                }
                if(node.right!=null){
                    n.add(node.right);
                }
                two.add(node.val);
            }
            list.add(0,two);
            next=n;
        }
        return list;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
